链接: https://www.luogu.org/problemnew/show/P1363
题目描述
背景 Background
（喵星人LHX和WD同心协力击退了汪星人的入侵，不幸的是，汪星人撤退之前给它们制造了一片幻象迷宫。）
WD：呜呜，肿么办啊……
LHX：momo…我们一定能走出去的！
WD：嗯，+U+U！
描述 Description
幻象迷宫可以认为是无限大的，不过它由若干个N*M的矩阵重复组成。矩阵中有的地方是道路，用’.’表示；有的地方是墙，用’#’表示。LHX和WD所在的位置用’S’表示。也就是对于迷宫中的一个点(x,y)，如果(x mod n,y mod m)是’.’或者’S’，那么这个地方是道路；如果(x mod n,y mod m)是’#’，那么这个地方是墙。LHX和WD可以向上下左右四个方向移动，当然不能移动到墙上。
请你告诉LHX和WD，它们能否走出幻象迷宫（如果它们能走到距离起点无限远处，就认为能走出去）。如果不能的话，LHX就只好启动城堡的毁灭程序了……当然不到万不得已，他不想这么做。。。
输入格式：
输入包含多组数据，以EOF结尾。
每组数据的第一行是两个整数N、M。
接下来是一个N*M的字符矩阵，表示迷宫里(0,0)到(n-1,m-1)这个矩阵单元。
输出格式
对于每组数据，输出一个字符串，Yes或者No。
input：
5 4
##.#
##S#
#..#
#.##
#..#
5 4
##.#
##S#
#..#
..#.
#.##
output：
Yes
No
解法：本题和一些常见的搜索迷宫题有一些区别。要求出能否达到出发点无限远处。
于是我们要怎么思考这个问题呢，首先考虑要不要扩展迷宫，发现不可行。因为如果扩展的话需要向八个方向进行扩展显然会MLE。如果同一个点被达到超过两次，则说明肯定能走到无穷远处。那么我们要怎么处理这个问题呢，我们可以用一个数组记录被访问的点，数组下标是取模以后的结果，同时访问时真实坐标，如果当前点的坐标不是原先访问时的坐标，则是说明能到达无穷远处。具体实现见代码。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
using namespace std;
const int maxn = 2e3;
char maz[maxn][maxn];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int n, m;
bool res;
int vis[maxn][maxn][3];
void dfs(int x, int y, int lx, int ly)
{
//如果一个点被第二次访问则说明可以走至无穷远
if(res == 1) return;
if(vis[x][y][0] && (vis[x][y][1] != lx || vis[x][y][2] != ly))
{
res = 1;
return;
}
vis[x][y][0] = 1;
vis[x][y][1] = lx;
vis[x][y][2] = ly;
for(int i = 0; i < 4; i++)
{
int px = lx + dx[i], py = ly + dy[i];
int a = (x + n + dx[i]) % n, b = (y + m + dy[i]) % m;
if(maz[a][b] != '#')
if(!vis[a][b][0] || vis[a][b][1] != px || vis[a][b][2] != py)
dfs(a, b, px, py);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
//freopen("/Users/vector/Desktop/in", "r", stdin);
while(cin >> n >> m)
{
for(int i = 0; i < n; i++)
cin >> maz[i];
memset(vis, 0, sizeof(vis));
res = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
{
if(maz[i][j] == 'S')
{
dfs(i, j, i, j);
break;
}
}
if(res) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}